#include <stdio.h>
#include <stdlib.h>
#include <math.h>
const MAXINT = 46340; 

static int OVERFLOW = 0;

int gcd(int, int);

int f(int x, int n){
	if (x>MAXINT) 
		OVERFLOW = 1;
	return ((x*x)+1)%n;
}


int prAlg(int n){
	int a,b,d,x,i;
	for (i=0; i <10; i++){
		x = ((rand()%n)+n)%n;
		a = b =x;
		do {
			a =	f(a,n);
			b = f(f(b,n),n);
			d = gcd(n,abs(a-b));
			if ((d != n) && (d != 1)) return d;  
		}
		while (a != b);
	}

	return 0;  
}


int gcd(int a, int b) {
	if (b > a)
		return gcd (b, a);
	else
	{
		int r;
		while (b != 0) 
		{
			r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
}

int main()
{
	int c, res;
	srand(100);
	
		printf(">>");
		scanf("%d", &c);
		if (c % 2 == 0)
			printf("\t2 is a factor\n");
		else {
			res = prAlg(c);
			if (res ==0)
				printf("\tProbably a prime\n");
			else 
				if (OVERFLOW)
					printf("\tError: Overflow occurred\n");
				else
					printf("\t= %d*%d\n", res,(c/res));
		     }
	return 0;
}


